package Sort;
/**
 * 时间复杂度：O(N*logN)
 * 空间复杂度：O(N)
 * 稳定性：稳定的排序
 */
public class MergeSort {
    public void Sort(int[] array)
    {

//        mergeSort(array, 0, array.length - 1);
        mergeNor(array);
    }

    private void mergeSort(int[] array, int start, int end) {
        if(start >= end) return;

        int mid = (start + end) / 2;
        mergeSort(array, start, mid);
        mergeSort(array, mid + 1, end);

        merge(array, start, mid, end);
    }

    private void mergeNor(int[] array) {
        int gap = 1;
        while (gap < array.length)
        {
            for(int i = 0; i < array.length; i += gap * 2)
            {
                int left = i;
                int mid = left + gap - 1;
                int right = mid + gap;
                if(mid >= array.length)
                {
                    mid = array.length - 1;
                }
                if(right >= array.length)
                {
                    right = array.length - 1;
                }

                merge(array, left, mid, right);
            }
            gap *= 2;
        }
    }

    private void merge(int[] array, int left, int mid, int right) {
        int s1 = left;
        int e1 = mid;
        int s2 = mid + 1;
        int e2 = right;

        int[] tmp = new int[right - left + 1];
        int k = 0;
        while(s1 <= e1 && s2 <= e2)
        {
            if(array[s1] <= array[s2])
            {
                tmp[k++] = array[s1++];
            }
            else {
                tmp[k++] = array[s2++];
            }
        }

        while(s1 <= e1)
        {
            tmp[k++] = array[s1++];
        }
        while (s2 <= e2)
        {
            tmp[k++] = array[s2++];
        }

        for(int i = 0; i < tmp.length; i++)
        {
            array[i + left] = tmp[i];
        }
    }
}
